package com.yj.search;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;

/**
 * 描述
 *
 * @author: yangjing
 * @date: 2023/10/25 15:25
 * @version: 1.0
 */
public class BinarySearch {
    public static int rank(int key, int[] a) {
        // 数组必须是有序的
        int lo = 0;
        int hi = a.length-1;
        while(lo <= hi) {
            // 被查找的键要么不存在，要么必然c存在于a[lo..hi]之中
            int mid = (lo+hi)/2;
            if(key < a[mid]) {
                hi = mid -1;
            } else if(key > a[mid]) {
                lo = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public static int rank1(int key,int l,int r, int[] a, int d) {
        for (int i = 0; i < d; i++) {
            System.out.printf(" ");
        }
        System.out.printf("%d %d\n", l, r);
        if(l>r) return -1;
        int mid = (l+r)/2;
        if(key<a[mid]) {
            return rank1(key, l,mid-1,a,d+1);
        } else if(key> a[mid]) {
            return rank1(key, mid+1,r,a,d+1);
        } else {
            return mid;
        }
    }

    public static void main(String[] args) {
        int[] whitelist = In.readInts("1.txt");
        Arrays.sort(whitelist);
        while(!StdIn.isEmpty()) {
            int key = StdIn.readInt();
            StdIn.readChar();
            char ch = StdIn.readChar();
            int i = rank1(key, 0, whitelist.length - 1, whitelist, 0);
            System.out.println(i);
            if(i >= 0 && ch == '+') {
                StdOut.println(key);
            } else if(i<0 && ch=='-') {
                StdOut.println(key);
            }
        }
    }
}
